Mergesort


How does Mergesort work?

	if size of array is 0 or 1, return
	recursively sort first and second halves
	merge two sorted halves into one
	(divide and conquer)


Give the array after the recursive calls sort each half.

	8 2 4 1 2 4

	2 4 8 1 2 4


How do you merge the sorted halves?

	allocate a temporary array
	repeatedly copy the smaller value from each half into the temp array
	when either half runs out, copy the rest of the other to temp array


Show the steps of merging the two arrays.

	1 2 4 8
	2 3 4 5


Show each step of Mergesort on the array.

	8 2 4 1 2 4

	mergesort 8 2 4
	    mergesort 8 2
	        mergesort 8
		    return 8
	        mergesort 2
		    return 2
		merge 8 and 2
		return 2 8
	    mergesort 4
	        return 4
	    merge 2 8 and 4
	    return 2 4 8
	mergesort 1 2 4
	    mergesort 1 2
	        mergesort 1
		    return 1
	        mergesort 2
		    return 2
		merge 1 and 2
		return 1 2
	    mergesort 4
	        return 4
	    merge 1 2 and 4
	    return 1 2 4
	merge 2 4 8 and 1 2 4
	return 1 2 2 4 4 8


    void mergeSort( Comparable [ ] a ) {
        mergeSort( a, 0, a.length - 1 );
    }

    void mergeSort( Comparable [ ] a, int left, int right ) {
        if( left < right ) {
            int center = ( left + right ) / 2;
            mergeSort( a, left, center );
            mergeSort( a, center + 1, right );
            merge( a, left, center, right );
        }
    }

    void merge( Comparable [ ] a, int left, int center, int right ) {
        int size = right - left + 1;
        Comparable [ ] tmp = new Comparable[ size ];
	int i = 0;
	int leftPos = left;
	int rightPos = center+1;
        while( leftPos <= center && rightPos <= right )
            if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
                tmp[ i++ ] = a[ leftPos++ ];
            else
                tmp[ i++ ] = a[ rightPos++ ];
        while( leftPos <= center )
            tmp[ i++ ] = a[ leftPos++ ];
        while( rightPos <= right )
            tmp[ i++ ] = a[ rightPos++ ];
        for( i = 0; i < size; i++ )
            a[ left+i ] = tmp[ i ];
    }


Can you prove MergeSort Works?


DEMO	(mergesort running time on sorted, reverse, random data)



What's a disadvantage of Mergesort?

	uses twice the memory


What kind of input is worst-case for Mergesort?

	doesn't matter


What's the Big-Oh bound for merge?

	O(n)


What's the Big-Oh bound for Mergesort?

	O(n log n)


How can you derive this bound?
What's the running time equation for Mergesort?

	T(n) = 2*T(n/2) + a*n
	T(1) = b
	(this is a recurrence relation)


How do you solve this recurrence relation?

	rewrite it without recursion
	T(1) = b
	T(2) = 2*T(1) + 2a = 2b + 2a
	T(4) = 2*T(2) + 4a = 4b + 8a
	T(8) = 2*T(4) + 8a = 8b + 24a

	T(n) = b*n + a*n log n


How can you see the Mergesort running time intuitively?

	draw a box with N columns and log N rows


How much merging work does Mergesort do at each level?

	work to merge at each level is N


How many levels can Mergesort recurse before hitting the base case?

	number of levels is logN because you divide by two each time



What's a Divide and Conquer Algorithm?

	divide problem into smaller subproblems of the same type
	solve the subproblems recursively
	combine the subproblem solutions into a solution for whole problem
	if the problem is small enough, solve it directly


What's the running time equation for divide and conquer algorithms?

	T(N) = A*T(N/B) + O(N^k)
	A is the number of subproblems
	B is the size of subproblems N/B
	k is the overhead O(N^k)


What's the solution to the general running time equation?

	for A >= 1 and B > 1,

	T(N) = O(N^(log[B]A))       for A > B^k
	T(N) = O(N^k log N)         for A = B^k
	T(N) = O(N^k)               for A < B^k


What are A, B, and k for Mergesort?

	A = 2
	B = 2
	k = 1


Show how the general solution gives O(N log N) for Mergesort.

	A = B^k
	T(N) = O(N^1 log N)